#include <sys/types.h>
#include <sys/tree.h>

#include <err.h>
#include <stdio.h>
#include <stdlib.h>

struct node {
   RB_ENTRY(node) entry;
   int ix;
};

int
compare(struct node *first, struct node *second)
{
   int retval;
   retval = (first->ix < second->ix ? -1 : first->ix > second->ix);

   printf("%d\n", retval);
   return retval;
}

RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
RB_GENERATE(inttree, node, entry, compare);

int testdata[] = {
   100, 10, 23, 45, 67, 89, 46, 78, 34, 58, 29, 93, 102, 111, 153, 371, 121,
   101, 27, 36, 56, 84, 91, 95, 97, 31, 37, 41, 47, 63, 1, 2, 3, 4, 5, 6, 7,
   343
};

void print_tree(struct node *nd)
{
   struct node *left, *right;
   if (nd != NULL) {
      left = RB_LEFT(nd, entry);
      right = RB_RIGHT(nd, entry);
      if (left == NULL && right == NULL)
         printf("%d", nd->ix);
      else {
         printf("%d(", nd->ix);
         print_tree(left);
         printf(",");
         print_tree(right);
         printf(")");
      }
   }
   else if (nd == NULL) {
      printf("nil");
   }
}

int
main()
{
   int ix;
   struct node *nd;

   for (ix = 0; ix < sizeof(testdata) / sizeof(testdata[0]); ix++) {
      if ((nd = malloc(sizeof(struct node))) == NULL)
         err(1, "malloc");
      nd->ix = testdata[ix];
      RB_INSERT(inttree, &head, nd);
   }

   RB_FOREACH(nd, inttree, &head) {
      printf("%d\n", nd->ix);
   }

   print_tree(RB_ROOT(&head));
   printf("\n");

   return 0;
}

